#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 要实现的功能：
// 创建，降幂排序，打印，相加

typedef struct Ploynode {
    float coef; // 系数
    int exp; // 指数
    struct Ploynode* next; // 指向下一个结点
} node;

node* CreatePloynode(void);
node* SortPloynode(node* head);
void PrintPloynode(node* head);
node* AddPloynode(node* head1, node* head2);
int GetLinkedLength(node* head);
void TailInsert(node* head, node* newnode);
node* CreateANode(float coef, int exp);

int main(int argc, char** argv)
{

    printf("输入系数与指数,末尾输入 0 0\n");

    printf("请输入多项式1:\n");
    node* head1 = CreatePloynode();
    printf("请输入多项式2:\n");
    node* head2 = CreatePloynode();

    printf("多项式1:\n");
    head1 = SortPloynode(head1);
    PrintPloynode(head1);
    printf("多项式2:\n");
    head2 = SortPloynode(head2);
    PrintPloynode(head2);

    printf("相加结果:\n");
    node* head3 = AddPloynode(head1, head2);
    PrintPloynode(head3);

    return 0;
}

// 创建一个链表
node* CreatePloynode(void)
{
    // head 用来做头指针, p 用来做前一个结点指针, s 用来做当前结点指针
    node* head = NULL;

    // c 是系数, e 是指数
    float c;
    int e;

    // 输入系数与指数
    scanf("%f %d", &c, &e);

    // 检查是否为 0 0
    while (c != 0.0f || e != 0) {
        // Create a node
        node* s = CreateANode(c, e);

        // 尾插新结点
        if (head == NULL) {
            head = s;
        } else {
            TailInsert(head, s);
        }

        // 输入下一轮数据
        scanf("%f %d", &c, &e);
    }

    return head; // 返回创建好的链表头结点
}

// 打印链表
void PrintPloynode(node* head)
{
    node* p = head;
    while (p != NULL) {
        printf("%.1fX^%d ", p->coef, p->exp);
        p = p->next;
    }

    printf("\n");
}

// 降幂排序
node* SortPloynode(node* head)
{
    // p 指向左边的结点
    node* p;
    // 2 个临时变量， 用来交换
    float tmp_f; // 系数
    int tmp_int; // 指数

    // 获取链表长度
    int length = GetLinkedLength(head);

    // 检查是否为一个结点
    if (length == 1) {
        return head;
    }

    // 排序
    for (int i = 1; i <= length - 1; i++) {
        p = head;
        for (int j = 0; j < length - i; j++) {

            // 如果右边大于左边
            // 交换
            if (p->next->exp > p->exp) {
                tmp_f = p->next->coef;
                tmp_int = p->next->exp;
                p->next->coef = p->coef;
                p->next->exp = p->exp;
                p->coef = tmp_f;
                p->exp = tmp_int;
            }
            p = p->next;
        }
    }

    return head;
}

// 合并已经排序了的链表
node* AddPloynode(node* head1, node* head2)
{
    // head3 用来存放合并后的链表
    node* head3 = NULL;
    // head1_ptr, head2_ptr 用来指向两个链表的头结点
    node* head1_ptr = head1;
    node* head2_ptr = head2;
    // 对比两个链表的头结点的指数
    // 如果头结点的指数相同，则将头结点的系数相加
    // 如果头结点的指数不同，则将头结点的指数较大的链表的头结点插入到 head3 中
    while (head1_ptr != NULL && head2_ptr != NULL) {
        // 创建一个结点用来存
        node* newnode = CreateANode(0.0f, 0);
        // 如果头结点的指数相同，则将头结点的系数相加
        if (head1_ptr->exp == head2_ptr->exp) {
            newnode->coef = head1_ptr->coef + head2_ptr->coef;
            newnode->exp = head1_ptr->exp;
            // 尾插新结点
            if (head3 == NULL) {
                head3 = newnode;
            } else {
                TailInsert(head3, newnode);
            }
            // 将两个链表的头结点指针后移一位
            head1_ptr = head1_ptr->next;
            head2_ptr = head2_ptr->next;
        } else if (head1_ptr->exp > head2_ptr->exp) {
            // 如果头结点的指数不同，则将头结点的指数较大的链表的头结点插入到 head3 中
            newnode->coef = head1_ptr->coef;
            newnode->exp = head1_ptr->exp;
            // 尾插新结点
            if (head3 == NULL) {
                head3 = newnode;
            } else {
                TailInsert(head3, newnode);
            }
            // 头结点指针后移一位
            head1_ptr = head1_ptr->next;
        } else {
            newnode->coef = head2_ptr->coef;
            newnode->exp = head2_ptr->exp;
            // 尾插新结点
            if (head3 == NULL) {
                head3 = newnode;
            } else {
                TailInsert(head3, newnode);
            }
            // 头结点指针后移一位
            head2_ptr = head2_ptr->next;
        }
    }

    // 检查是否还有剩余的结点
    // 如果有就追加到 head3 中
    if (head1_ptr != NULL) {
        // 遍历 head1_ptr 的剩余结点
        while (head1_ptr != NULL) {
            node* newnode = CreateANode(head1_ptr->coef, head1_ptr->exp);
            if (head3 == NULL) {
                head3 = newnode;
            } else {
                TailInsert(head3, newnode);
            }
            head1_ptr = head1_ptr->next;
        }
    } else if (head2_ptr != NULL) {
        // 遍历 head2_ptr 的剩余结点
        while (head2_ptr != NULL) {
            node* newnode = CreateANode(head2_ptr->coef, head2_ptr->exp);
            if (head3 == NULL) {
                head3 = newnode;
            } else {
                TailInsert(head3, newnode);
            }
            head2_ptr = head2_ptr->next;
        }
    }

    return head3; // 返回合并后的链表
}

// 获取链表的长度
int GetLinkedLength(node* head)
{
    int length = 0;
    node* p = head;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

// 尾插法
void TailInsert(node* head, node* newnode)
{
    node* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newnode;
}

// 创建一个结点
node* CreateANode(float coef, int exp)
{
    node* newnode = (node*)malloc(sizeof(node));
    newnode->coef = coef;
    newnode->exp = exp;
    newnode->next = NULL;
    return newnode; // 返回创建的结点的地址
}
